#include<iostream>
#include<algorithm>
using namespace std;
//带头双向循环链表
template<class T>
struct ListNode
{
  ListNode<T>* next;
  ListNode<T>* prev;
  T val;
  ListNode(const  T& v)
    :val(v),next(nullptr),prev(nullptr)
  {}
};

template<class T>
class DoubleList
{
public:
  DoubleList()
  {
    phead = new ListNode<T>(-1);
  }
  ~DoubleList()
  {
    ListNode<T>* cur = phead->next;
    while(cur != phead)
    {
      ListNode<T>* next = cur->next;
      delete cur;
      cur = next;
    }
    //最后释放哨兵位
    delete phead;
    phead = nullptr;
  }
  void PrintDoubleList()
  {
    ListNode<T>* cur = phead->next;
    while(cur != phead)
    {
      cur << cur->val << " ";
      cur = cur->next;
    }
    cout << endl;
  }
  void push_back(const T& v)
  {
    ListNode<T>* tail = phead->prev;
    ListNode<T>* newnode = new ListNode<T>(v);
    //tail nennode phead 
    tail->next = newnode;
    newnode->prev = tail;
    phead->prev = newnode;
    newnode->next = phead;
  }
  void pop_back()
  {
    assert(phead->next != phead);//不能删除哨兵位
    ListNode<T>* tail = phead->prev;
    ListNode<T>* prev = tail->prev;
    phead->prev = prev;
    prev->next = phead;
    delete tail;
  }
  void push_front(const T& v)
  {
    ListNode<T>* head = phead->next; 
    ListNode<T>* newnode = new ListNode<T>(v);
    //phead newnode head 
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = head;
    head->prev = newnode;
  }
  void pop_front()
  {
    assert(phead->next != phead);
    ListNode<T>* del = phead->next;
    phead->next = del->next;
    del->next->prev = phead;
    delete del;
  }
  ListNode<T>* findNodeFronHead(const T& v)
  {
    ListNode<T>* cur = phead->next;
    while(cur != phead)
    {
      if(cur->val == v)
        return cur;
      cur = cur->next;
    }
    return nullptr;
  }
  ListNode<T>* findNode(ListNode<T>* pos,const T& v)
  {
    ListNode<T>* cur = pos;
    while(cur != phead)
    {
      if(cur->val == v)
        return cur;
      cur = cur->next;
    }
    return nullptr;
  }
  void push_front_pos(ListNode<T>* pos,const T& v)
  {
    ListNode<T>* newnode = new ListNode<T>(v);
    ListNode<T>* prev = pos->prev;
    //prev newnode pos 
    prev->next = newnode;
    newnode->prev = prev;
    newnode->next = pos;
    pos->prev = newnode;
  }
  void pop_back_pos(ListNode<T>* pos)
  {
    assert(pos != phead);
    assert(pos);
    ListNode<T>* prev = pos->prev;
    ListNode<T>* next = pos->next;
    prev->next = next;
    next->prev = prev;
    delete pos;
  }
private:
  ListNode<T>* phead;//哨兵位节点
};
